package com.dbh.alg.algorithm.hot100.链表;

import com.dbh.alg.algorithm.hot100.ListNode;

import java.util.ArrayList;
import java.util.List;

public class Leetcode148_排序链表 {


    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(new ListNode(head.val));
            head = head.next;
        }
        return split(list, 0, list.size() - 1);
    }

    private ListNode split(List<ListNode> list, int i, int j) {
        if (i == j) {
            return list.get(i);
        }
        int mid = (i + j) >>> 1;
        ListNode left = split(list, i, mid);
        ListNode right = split(list, mid + 1, j);
        return mergeTwoListNode(left, right);
    }

    private ListNode mergeTwoListNode(ListNode p1, ListNode p2) {
        if (p1 == null) {
            return p2;
        }
        if (p2 == null) {
            return p1;
        }
        if (p1.val < p2.val) {
            p1.next = mergeTwoListNode(p1.next, p2);
            return p1;
        } else {
            p2.next = mergeTwoListNode(p1, p2.next);
            return p2;
        }
    }
}
